

//160. 相交链表
//编写一个程序，找到两个单链表相交的起始节点。
//输入：intersectVal = 8, listA = [4, 1, 8, 4, 5], listB = [5, 0, 1, 8, 4, 5], skipA = 2, skipB = 3
//输出：Reference of the node with value = 8
//输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
//从各自的表头开始算起，链表 A 为[4, 1, 8, 4, 5]，链表 B 为[5, 0, 1, 8, 4, 5]。
//在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。




#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack> 
#include <map> 
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;


struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void print(ListNode *head)   
{
    ListNode *p = head;
    while (p != NULL)
    {
        cout << p->val;
        p = p->next;
    }
}



//A的指针遍历完A 接着从headB开始遍历
//B的指针遍历完B 接着从headA开始遍历
//两个指针都最多走m + n + 1步。
//当两个指针同时为空时，表示不相交；当两个都非空且相等时，表示相交

//时间复杂度O(m + n)  空间复杂度O(1)

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    if (headA == nullptr || headB == nullptr)
        return nullptr;

    ListNode *p1 = headA;
    ListNode *p2 = headB;

    while (p1 != p2)
    {
        if (p1 == nullptr)
            p1 = headB;
        else
            p1 = p1->next;

        if (p2 == nullptr)
            p2 = headA;
        else
            p2 = p2->next;
    }
    return p1;
}



int main()
{
    ListNode* head = new ListNode(1);
    ListNode* list = head;
    list->next = new ListNode(2);
    list = list->next;
    list->next = new ListNode(3);
    list = list->next;
    list->next = new ListNode(4);

    print(head);
    system("pause");

    ListNode* res = getIntersectionNode(head, head);

    cout << res << endl;
    system("pause");

    return 0;
}












